####
#深度优先遍历的方法来求解，但是这种方式会超时
def dg(choice,cur_stage,n,res):
    '''
    :param choice:此次行动选择的台阶数
    :param cur_stage: 当前已经走过的台阶数
    :return: 符合条件的走法的总次数
    '''
    cur_stage+=choice
    #出口函数
    if cur_stage>n:
        cur_stage-=choice
        return None
    if cur_stage==n:
        print("当前到达了一次")
        res[0]+=1
        print("------------------------")
        return None
    print("当前选择值：",choice)
    print("the_stage:",cur_stage)
    dg(1,cur_stage,n,res)
    dg(2,cur_stage,n,res)
def climbStairs(n):
    res=[0]
    dg(0,0,n,res)
    print(res[0])
#超时
# climbStairs(38)

def climbStairs_1(n):
    if n<=2:
        return n
    dp=[1 for _ in range(n+1)]
    for i in range(2,n+1):
        dp[i]=dp[i-1]+dp[i-2]
    return dp[n]
print(climbStairs_1(38))
def climbStairs_2(n):
    if n<=2:
        return n
    dp=[1 for _ in range(3)]
    for i in range(2,n+1):
        dp[2]=dp[1]+dp[0]
        dp[0]=dp[1]
        dp[1]=dp[2]
    return dp[2]
print(climbStairs_2(38))
